package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         112,
		Discription: "是否有从根节点到叶子节点的为指定值的路径之和",
		Level:       2,
		Labels: map[string]int{
			"回溯":  1,
			"二叉树": 1,
		},
	})
}

func HasPathSum(root *ds.TreeNode, targetSum int) bool {
	var hasSum func(*ds.TreeNode, int) bool
	hasSum = func(node *ds.TreeNode, sum int) bool {
		//判空放最前面
		if node == nil {
			return false
		}

		sum += node.Val
		//是叶子节点且值满足targetSum的情况下才返回true
		if node.Left == nil && node.Right == nil && sum == targetSum {
			return true
		}

		return hasSum(node.Left, sum) || hasSum(node.Right, sum)
	}

	return hasSum(root, 0)
}
